package newcoder;
/*
题目描述
        在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
        [
        [1,2,8,9],
        [2,4,9,12],
        [4,7,10,13],
        [6,8,11,15]
        ]
        给定 target = 7，返回 true。
        给定 target = 3，返回 false。
*/

public class newcoder_1_FindTarget {
    //方法一：暴力法，两重循环逐元素查找;但是没有利用题目的性质
    public boolean Find_1(int target, int [][] array) {
        int m=array.length;
        int n=array[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (target==array[i][j]){
                    return true;
                }
            }
        }
        return false;
    }

    //方法2：从左下角开始找，比target大则上移动，小则右移动
    public boolean Find_2(int target, int [][] array) {
        int rows = array.length;
        if(rows == 0){
            return false;
        }
        int cols = array[0].length;
        if(cols == 0){
            return false;
        }
        // 左下
        int row = rows-1;
        int col = 0;
        while(row>=0 && col<cols){
            if(array[row][col] < target){
                col++;
            }else if(array[row][col] > target){
                row--;
            }else{
                return true;
            }
        }
        return false;
    }

    //方法三：利用二分查找
    //假设arr数组，val，tar如下图所示：
    //如果我们把二分值定在右上角或者左下角，就可以进行二分。这里以右上角为例，左下角可自行分析：

    //1）我么设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]
    //2）接下来进行二分操作：
    //3）如果val == target,直接返回
    //4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]
    //5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]
    //6）继续步骤2）

    //时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
    //空间复杂度：O(1)
    public boolean Find_3(int target, int [][] array) {
        // 判断数组是否为空
        int m = array.length;
        if (m == 0)
            return false;
        int n = array[0].length;
        if (n == 0)
            return false;
        int r = 0, c = n-1; // 右上角元素
        while (r<m && c>=0)
        {
            if (target == array[r][c]) {
                return true;
            }
            else if (target > array[r][c]) {
                ++r;
            }
            else {
                --c;
            }
        }
        return false;
    }



    public static void main(String[] args) {
        newcoder_1_FindTarget sample=new newcoder_1_FindTarget();
    }
}
